package com.shiguiwu.springmybatis.leetcode.greenhand;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @description: 新手村
 * @author: stone
 * @date: Created by 2022/5/27 16:21
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.leetcode.greenhand
 */
public class GreenHandTests {


    public static void main(String[] args) {
        //fizzBuzz(15);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        middleNode(node1);



    }


    /**
     * 一维数组的动态和
     * <p>
     * 给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
     * <p>
     * 请返回 nums 的动态和。
     * <p>
     * 输入：nums = [1,2,3,4]
     * 输出：[1,3,6,10]
     * 解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
     *
     * @param nums
     * @return
     */
    public static int[] runningSum(int[] nums) {
        int[] run = new int[nums.length];
        int t = 0;
        for (int i = 0; i < nums.length; i++) {
            t += nums[i];
            run[i] = t;

        }

        return run;
    }


    /**
     * 赎金信
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     * <p>
     * 如果可以，返回 true ；否则返回 false 。
     * <p>
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     * <p>
     * 输入：ransomNote = "aa", magazine = "ab"
     * 输出：false
     * <p>
     * 输入：ransomNote = "aa", magazine = "aab"
     * 输出：true
     *
     * @param ransomNote 源字符串
     * @param magazine   字符构成
     * @return true
     */
    public static boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }

        char[] chars = ransomNote.toCharArray();

        //Set<Character> set = new HashSet<>(chars.length);
        Map<Character, Integer> hash = new HashMap<>();

        //int[] counts = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            char t = chars[i];
            if (!magazine.contains(String.valueOf(t))) {
                return false;
            }
            if (hash.containsKey(t)) {
                Integer integer = hash.get(t);
                hash.put(t, ++integer);
            } else {
                hash.put(t, 1);
            }

        }
        //boolean flag = false;
        //hash.forEach((k,v) -> {
        //    String replace = magazine.replace(String.valueOf(k), "");
        //    flag
        //});

        Set<Map.Entry<Character, Integer>> entries = hash.entrySet();
        for (Map.Entry<Character, Integer> next : entries) {
            Character key = next.getKey();
            String replace = magazine.replace(String.valueOf(key), "");
            if ((magazine.length() - replace.length()) < next.getValue()) {
                return false;
            }
        }
        return true;


        /**
         * 效率高的思路
         * //记录杂志字符串出现的次数
         * int[] arr = new int[26];
         * int temp;
         * for (int i = 0; i < magazine.length(); i++) {
         * temp = magazine.charAt(i) - 'a';
         * arr[temp]++;
         * }
         * for (int i = 0; i < ransomNote.length(); i++) {
         * temp = ransomNote.charAt(i) - 'a';
         * //对于金信中的每一个字符都在数组中查找
         * //找到相应位减一，否则找不到返回false
         * if (arr[temp] > 0) {
         * arr[temp]--;
         * } else {
         * return false;
         * }
         * }
         * return true;
         */
    }


    /**
     * 给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：
     * <p>
     * answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
     * answer[i] == "Fizz" 如果 i 是 3 的倍数。
     * answer[i] == "Buzz" 如果 i 是 5 的倍数。
     * answer[i] == i （以字符串形式）如果上述条件全不满足。
     *
     * @param n
     * @return
     */
    public static List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {

            if (i % 3 == 0 && i % 5 == 0) {
                list.add("FizzBuzz");
            } else if (i % 3 == 0) {
                list.add("Fizz");
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(String.valueOf(i));
            }

        }
        return list;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    /**
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
     * @param head
     * @return
     */
    public static ListNode middleNode(ListNode head) {
        ListNode p = head;
        ListNode q = head;

        while (p != null && p.next != null) {
            p = p.next.next;
            q = q.next;
        }
        return q;
    }

    //
    //给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；
    //否则，减去 1 。

    /**
     * 输入：num = 14
     * 输出：6
     * 解释：
     * 步骤 1) 14 是偶数，除以 2 得到 7 。
     * 步骤 2） 7 是奇数，减 1 得到 6 。
     * 步骤 3） 6 是偶数，除以 2 得到 3 。
     * 步骤 4） 3 是奇数，减 1 得到 2 。
     * 步骤 5） 2 是偶数，除以 2 得到 1 。
     * 步骤 6） 1 是奇数，减 1 得到 0 。
     *

     * @param num
     * @return
     */
    public static int numberOfSteps(int num) {
        int res = 0;
        while (  num != 0) {
            if(num % 2 == 0) {
                num = num / 2;

            }
            else {
                num = num - 1;

            }
            res++;

        }
        return res;
    }


    /**
     * 给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i​​​​​​​​​​​​ 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
     *
     * 客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户
     *

     * @param accounts
     * @return
     *
     * 输入：accounts = [[1,2,3],[3,2,1]]
     * 输出：6
     * 解释：
     * 第 1 位客户的资产总量 = 1 + 2 + 3 = 6
     * 第 2 位客户的资产总量 = 3 + 2 + 1 = 6
     * 两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。
     *
     */

    public static int maximumWealth(int[][] accounts) {
        int sum = 0;
        for (int[] account : accounts) {
            int t = 0;
            for (int value : account) {
                t += value;
            }
            sum = sum > t? sum:t;

        }
        return sum;
    }



}
